package com.sgg.algorithm.sort;

public class InsertSort {
    public static void main(String[] args) {
    }

    /**
     * 前面是有序的,后面是无序的,每次就是把无序的第一个正确的插入到前面
     * 自己的思路 效率慢
     */
    public static void sort(int[] arr) {
        int length = arr.length;

        for (int i = 1; i < length; i++) {
            for (int j = i; j > 0; j--) {
                exchange(arr, j - 1, j);
            }
        }
    }

    public static void exchange(int[] arr, int index1, int index2) {
        if (index1 > arr.length - 1 || index2 > arr.length - 1) {
            throw new RuntimeException("下标越界");
        }
        if (arr[index1] > arr[index2]) {
            int temp = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = temp;
        }

    }

    /**
     * 老师的思路
     */
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];//先记录插入的值,后面被覆盖
            int insertIndex = i - 1;//需要插入的位置
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];//满足条件,就把旗子往后面移动
                insertIndex--;
            }
            arr[insertIndex + 1] = insertVal;//最后把要插入的放进去,巧妙
        }
    }

    /**
     * 老师的思路优化
     */
    public static void insertSortImprove(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];
            int insertIndex = i - 1;
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            if (insertIndex + 1 != i) {
                arr[insertIndex + 1] = insertVal;
            }
        }
    }

}